package com.example.demo.algorithm.linear;

import java.util.Iterator;

/**
 * @Author: xiatian
 * @CreateTime: 2021/12/30 2:10 下午
 * @Description:队列
 */
public class Queue<T> implements Iterable<T> {
    private Node head;
    private Node last;
    private int N;

    public Queue() {
        this.head = new Node(null, null);
        last = null;
        this.N = 0;
    }


    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 返回队列中元素的个数
     *
     * @return
     */
    public int size() {
        return N;
    }

    /**
     * 入队
     *
     * @param t
     */
    public void enqueue(T t) {
        if (last == null) {
            last = new Node(t, null);
            head.next = last;
        } else {
            Node oldLast = last;
            Node n = new Node(t, null);
            oldLast.next = n;
            last = n;
        }
        N++;
    }

    /**
     * 出队列
     *
     * @return
     */
    public T dequeue() {
        if (last == null) {
            return null;
        } else {
            Node oldFirst = head.next;
            head.next = oldFirst.next;
            N--;
            if (isEmpty()) {
                last = null;
            }
            return oldFirst.item;
        }

    }

    @Override
    public Iterator<T> iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator<T> {
        private Node n = head;


        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public T next() {
            n = n.next;
            return n.item;
        }
    }


    private class Node {
        public T item;
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }


}
